#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 069. Sqrt(x) x 的平方根 .py
@time: 2022/1/14 19:42
@desc: https://leetcode-cn.com/problems/sqrtx/
> 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

@解题思路：
    1. 数学
    2. 二分:Ot(logX), Os(1)
'''
import math
class Solution1(object):
    """
    数学推导
    """
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        # √x = x^(1/2) = e^ln(x^(1/2)) = e^1/2lnx
        if x==0: return 0
        ans = int(math.exp(0.5*math.log(x)))
        return ans+1 if (ans+1)**2<=x else ans

class Solution2(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0: return 0
        low, high, ans = 0, x, -1
        while low<=high:
            mid = (low+high)//2
            if mid*mid<=x:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        return ans